package iolab;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.StreamTokenizer;
import java.util.Random;

public class TspSimple {
	Random generator = new Random();

	/*
	 * Liczba miast (wierzchoĹ‚kĂłw)
	 */
	int nodeNumber;

	/*
	 * Dwuwymiarowa tablica odlegĹ‚oĹ›ci miÄ™dzy miastami
	 */
	int[][] distances;

	/*
	 * Tablica przechowujÄ…ca rozwiazanie
	 *
	 * nextNodes[a] == b oznacza, ĹĽe nastÄ™pnikiem miasta (wierzchoĹ‚ka) a
	 * w rozwiÄ…zaniu jest miasto (wierzchoĹ‚ek) b
	 *
	 * Warunki poprawnoĹ›ci:
	 * 1. nextNodes[a] == b <=> previousNodes[b] == a
	 * 2. 0 <= nextNodes[...] < nodeNumber
	 * 3. opisywana Ĺ›cieĹĽka przechodzi przez wszystkie miasta dokĹ‚adnie
	 *    jeden raz
	 */
	int[] nextNodes;
	

	/*
	 * Tablica przechowujÄ…ca rozwiazanie
	 *
	 * previousNodes[a] == b oznacza, ĹĽe poprzednikiem miasta (wierzchoĹĽka) a
	 * w rozwiÄ…zaniu jest miasto (wierzchoĹ‚ek) b
	 *
	 * Uwaga: Tablica jest nadmiarowa w stosunku do nextNodes, ale jej uĹĽycie
	 * zwiÄ™ksza efektywnoĹ›Ä‡
	 *
	 * Warunki poprawnoĹ›ci:
	 * 1. previousNodes[a] == b <=> nextNodes[b] == a
	 * 2. 0 <= previousNodes[...] < nodeNumber
	 * 3. opisywana Ĺ›cieĹĽka przechodzi przez wszystkie miasta dokďż˝adnie
	 *    jeden raz
	 */
	int[] previousNodes;

	/*
	 * WartoĹ›Ä‡ funkcji celu (dĹ‚ugoĹ›Ä‡ Ĺ›cieĹĽki)
	 *
	 * Warunki poprawnoĹ›ci:
	 * 1. objective > 0 (teoretycznie wartoĹ›Ä‡ 0 jest dopuszczalna, ale
	 *    w praktycznych instancjach nie moĹĽe siÄ™ pojawiÄ‡)
	 * 2. objective jest rĂłwne sumie Distance(a, nextNodes[a])
	 *    po a = 0, ..., nodeNumber-1
	 */
	int objective;

	/*
	 * Zwraca odlegĹ‚oĹ›Ä‡ pomiÄ™dzy dwoma miastami
	 */
	public int getDistance(int n1, int n2)
	{
		return distances[n1][n2];
	}

	/*
	 * Ĺ�aduje instancjÄ™ danych z pliku
	 */
	public boolean loadInstance(String filePath) {
		try {
	        BufferedReader reader = new BufferedReader(new FileReader(filePath));
	        StreamTokenizer input = new StreamTokenizer(reader);

	        // wczytaj liczbÄ™ miast
	        input.nextToken();
	        nodeNumber = (int) input.nval;
	        //System.out.println("zzzzzzzzzzzzz" + nodeNumber);
	        assert nodeNumber > 0;

	        distances = new int[nodeNumber][nodeNumber];
	        nextNodes = new int[nodeNumber];
	        previousNodes = new int[nodeNumber];

	        for (int i = 0; i < nodeNumber; i++) {
		        for (int j = 0; j < nodeNumber; j++) {
		        	// wczytaj odlegĹ‚oĹ›Ä‡ miÄ™dzy miastami (i, j)
		        	input.nextToken();
		        	distances[i][j] = (int) input.nval;
		        }
	        }

	        reader.close();
	    } catch (IOException e) {
	    	return false;
	    }

	    return true;
	}

	/*
	 * Konstruuje rozwiÄ…zanie poczÄ…tkowe odpowiadajÄ…ce losowej permutacji miast
	 */
	public void findRandom() {
		boolean[] nodeAdded = new boolean[nodeNumber];
		int firstNode = generator.nextInt(nodeNumber);
		int node = firstNode;

		// dodawaj losowo kolejne miasta do Ĺ›cieĹĽki
		for (int i = 0; i < nodeNumber - 1; i++) {
			nodeAdded[node] = true;
			

			// wylosuj miasto niedodane jeszcze do Ĺ›cieĹĽki
			int nextNode = generator.nextInt(nodeNumber);
			//0 <= nextNodes[...] < nodeNumber
			while (nodeAdded[nextNode]) {
				nextNode = (nextNode + 1) % nodeNumber;
			}

			// dodaj Ĺ‚uk (node, nextNode)
			nextNodes[node] = nextNode;
			previousNodes[nextNode] = node;
			assert (nextNodes[node] == nextNode) == (previousNodes[nextNode] == node);

			// weĹş nastÄ™pne miasto
			node = nextNode;
		}

		// dodaj Ĺ‚uk (node, firstNode)
		nextNodes[node] = firstNode;
		assert nextNodes[node] > 0;
		assert nodeNumber > nextNodes[node];
		//nextNodes[...] < nodeNumber
		previousNodes[firstNode] = node;
		assert (nextNodes[node] == firstNode) == (previousNodes[firstNode] == node);


		// oblicz wartoĹ›Ä‡ funkcji celu
		objective = 0;
		for (int i = 0; i < nodeNumber; i++) {
			objective += getDistance(i, nextNodes[i]);
			assert objective > 0;
		}
	}

	/*
	 * Konstruuje rozwiÄ…zanie poczÄ…tkowe wykorzystujÄ…ce zachĹ‚anny algorytm
	 * wyboru miast
	 */
	public void findGreedy() {
		boolean[] nodeAdded = new boolean[nodeNumber];
		int firstNode = generator.nextInt(nodeNumber);
		int node = firstNode;

		// dodawaj losowo kolejne miasta do Ĺ›cieĹĽki
		for (int i = 0; i < nodeNumber - 1; i++) {
			nodeAdded[node] = true;
			//assert ;
			// dodaj "najlepsze" miasto do Ĺ›cieĹĽki
			int bestDistance = Integer.MAX_VALUE;
			int bestNode = -1;
			for (int j = 0; j < nodeNumber; j++) {
				if (!nodeAdded[j] && getDistance(node, j) < bestDistance) {
					bestDistance = getDistance(node, j);
					bestNode = j;
				}
			}

			// dodaj Ĺ›uk (node, bestNode)
			nextNodes[node] = bestNode;
			previousNodes[bestNode] = node;

			// weĹĽ nastÄ™pne miasto
			node = bestNode;
		}

		// dodaj Ĺ‚uk (node, firstNode)
		nextNodes[node] = firstNode;
		assert nextNodes[node] > 0;
		assert nodeNumber > nextNodes[node];
		previousNodes[firstNode] = node;

		// oblicz wartoĹ›Ä‡ funkcji celu
		objective = 0;
		for (int i = 0; i < nodeNumber; i++) {
			objective += getDistance(i, nextNodes[i]);
		}
	}

	public void printSolution()
	{
		System.out.println("Objective: " + objective);

		int node = 0;
		for (int i = 0; i < nodeNumber; i++) {
			System.out.print(node + " ");
			node = nextNodes[node];
			//nextNodes[a] == b <=> previousNodes[b] == a
		}
		System.out.println();
	}

	public static void main(String[] args) {
		TspSimple tspSimple = new TspSimple();

		tspSimple.loadInstance("data/test.txt");

		tspSimple.findRandom();
		tspSimple.printSolution();
		tspSimple.findGreedy();
		tspSimple.printSolution();
	}
}
